using System;
using System.Collections.Generic;

namespace Test.ConsoleProgram.Algorithm.Solution
{
    [TestDescription("算法: 0659. 分割数组为连续子序列")]
    public class No0659_IsPossible : AbsBaseTestItem
    {
        /*
        给你一个按升序排序的整数数组 num（可能包含重复数字），请你将它们分割成一个或多个子序列，其中每个子序列都由连续整数组成且长度至少为 3 。
        如果可以完成上述分割，则返回 true ；否则，返回 false 。
        示例 1：
            输入: [1,2,3,3,4,5]
            输出: True
            解释:
                你可以分割出这样两个连续子序列 :
                1, 2, 3
                3, 4, 5
        示例 2：
            输入: [1,2,3,3,4,4,5,5]
            输出: True
            解释:
                你可以分割出这样两个连续子序列 :
                1, 2, 3, 4, 5
                3, 4, 5
        示例 3：
            输入: [1,2,3,4,4,5]
            输出: False
        提示：
            输入的数组长度范围为 [1, 10000]
        */

        public override void OnTest()
        {
            OnTest(IsPossible_GreedyCalc);
        }

        private void OnTest(Func<int[], bool> func)
        {
            Assert.TestExe(func, new int[] { 1, 2, 3, 3, 4, 5 }, true);
            Assert.TestExe(func, new int[] { 1, 2, 3, 3, 4, 4, 5, 5 }, true);
            Assert.TestExe(func, new int[] { 1, 2, 3, 4, 4, 5 }, false);
        }

        /// <summary>
        /// 贪心算法
        /// https://leetcode-cn.com/problems/split-array-into-consecutive-subsequences/solution/tan-xin-suan-fa-by-jiu-yao-7-8tj4/
        /// </summary>
        public bool IsPossible_GreedyCalc(int[] nums)
        {
            int max = nums[nums.Length - 1] - nums[0] + 1;
            int[] save = new int[max];
            foreach (int i in nums)
            {
                save[i - nums[0]]++;
            }
            List<int[]> thesave = new List<int[]>();
            for (int i = 0; i < max; i++)
            {
                for (int j = thesave.Count - 1; j > -1 && save[i] > 0; j--)
                {
                    if (i - thesave[j][1] == 1)
                    {
                        thesave[j][1]++;
                        save[i]--;
                    }
                    else
                    {
                        if (thesave[j][1] < thesave[j][0] + 2)
                            return false;
                        thesave.Remove(thesave[j]);
                    }
                }
                while (save[i] > 0)
                {
                    thesave.Add(new int[] { i, i });
                    save[i]--;
                }
            }
            foreach (int[] i in thesave)
            {
                if (i[1] < i[0] + 2)
                    return false;
            }
            return true;
        }
    }
}
